#include "MergeSort.h"

MergeSort::MergeSort(void)
{
}

MergeSort::~MergeSort(void)
{
}


void MergeSort::doMerge(vector<int> &A, int p, int q, int r)
{
	int n1, n2, i, j;
	n1 = q - p + 1;
	n2 = r - q;

	vector<int> L;
	vector<int> R;

	L.resize(n1+1);
	R.resize(n2+1);

	for(i=0; i < n1; i++)
	{
		L[i] = A[p+i-1];
	}

	for(j=0; j < n2; j++)
	{
		R[j] = A[q+j];
	}

	i = 0;
	j = 0;

	for(int k=p; k <= r; k++)
	{
		k;
		if ((L[i] <= R[j] && i < n1) || j >= n2)
		{
			A[k-1] = L[i];
			i=i+1;
		}
		else
		{
			A[k-1] = R[j];
			j=j+1;
		}
	}
}

void MergeSort::doMergeSort(vector<int> &A, int p, int r)
{
	int q;
	double d;
	if (p < r)
	{
		d = (p + r) / 2;
		q = (int)floor(d);
		this->doMergeSort(A, p, q);
		this->doMergeSort(A, q+1, r);
		this->doMerge(A, p, q, r);
	}
}